package gold.enterprise;

import java.util.PriorityQueue;

/**
 * Created by fanzhenyu02 on 2020/7/29.
 */
public class Amazon {


//Given n ropes of different lengths, we need to connect these ropes into one rope.
//We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths.
//The length of this connected rope is also equal to the sum of their lengths.
//This process is repeated until n ropes are connected into a single rope.
//Find the min possible cost required to connect all ropes.
//Input: ropes = [20, 4, 8, 2]
//        Output: 54
//
//        2+4=6
//        6+8=14
//        14+20=34
//        sum=6+14+34=54


    class Solution {
        Solution() {
        }

        public int minCostRopeMerge(int[] ropes) {
            //ropes will be empty or null. so we need to jude that.
            if (null == ropes || ropes.length <= 0) return -1;
            if (ropes.length == 1) return ropes[0];

            // start normal situation process.
            int sum = 0;
            PriorityQueue<Integer> pri = new PriorityQueue();
            for (int i = 0; i < ropes.length; ++i) {
                pri.add(ropes[i]);
            }

            // using Integer.MAX_VALUE to tell that already the last rope.
            pri.add(Integer.MAX_VALUE);
            while (!pri.isEmpty()) {
                int mergeRopeFirst = pri.poll();
                int mergeRopeSecond = pri.poll();
                if (mergeRopeSecond == Integer.MAX_VALUE) return sum;//this is already the fianl rope.

                int mergeEdRope = mergeRopeFirst + mergeRopeSecond;
                sum += mergeEdRope;
                pri.add(mergeEdRope);
            }

            return -1;
        }
    }

    public void run() {
        int[] ropes = {1, 2, 3, 4};
        Solution solution = new Solution();
        System.out.println(solution.minCostRopeMerge(ropes));
    }

}

